package tianhao.luo.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 插值查找算法
 *
 * @author: tianhao.luo@hand-china.com 2021/6/19  17:00
 */
public class InsertValueSearch {
    private int[] array;

    public InsertValueSearch(int[] array) {
        this.array = array;
    }


    /**
     * 插值查找算法也需要数组是有序的
     * 查找到一个元素就返回
     * @param value 待查找的值
     * @param left 左边的索引
     * @param right 右边的索引
     * @return 找到的元素索引
     */
    public int search(int value,int left,int right){
        System.out.println("hello~");
        // 如果left大于right就要退出循环了
        // 大于最大值或小于最小值也要退出循环
        // 同时我们计算出来的mid可能越界,例如:我们要查询一个极大的数,value-array[left]可以看为无限大,那么计算出来的mid可以看为无限大
        if (left>right || value<array[0] || value>array[array.length-1]){
            return -1;
        }

        // 将二分查找法的mid索引的计算方式修改
        int mid = left + (right-left) * (value-array[left])/(array[right]-array[left]);

        // 大于中间值,向右扫描
        if (value>array[mid]){
            return search(value,mid+1,right);
        } else if (value<array[mid]) {
            // 向左扫描
            return search(value,left,mid-1);
        }else {
            return mid;
        }
    }


    /**
     * 查找到所有相同的元素
     * @param value 待查找的值
     * @param left 左边的索引
     * @param right 右边的索引
     * @return 找到的元素索引
     */
    public List<Integer> searchTwo(int value, int left, int right){
        System.out.println("hello~");
        // 如果left大于right就要退出循环了
        // 大于最大值或小于最小值也要退出循环
        if (left>right || value<array[0] || value>array[array.length-1]){
            return new ArrayList<>();
        }

        // 将二分查找法的mid索引的计算方式修改
        int mid = left + (right-left) * (value-array[left])/(array[right]-array[left]);

        // 大于中间值,向右扫描
        if (value>array[mid]){
            return searchTwo(value,mid+1,right);
        } else if (value<array[mid]) {
            // 向左扫描
            return searchTwo(value,left,mid-1);
        }else {
            // 找到匹配位置,还需要向左和向右查找
            // 向左搜索
            List<Integer> list = new ArrayList<>();

            int temp=mid-1;
            while (true){
                // 超出数组最小索引
                if (temp<0 || array[temp] != value){
                    break;
                }
                list.add(temp);
                temp--;
            }

            list.add(mid);

            temp = mid+1;
            while (true){
                // 超出数组最大长度
                if (temp>array.length-1 || array[temp] != value){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }
    }
}
